class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        mysort(stock,0,stock.size()-1,cnt);
        return {stock.begin(),stock.begin()+cnt};
    }

    int getrand(vector<int>& stock,int l,int r)
    {
        return stock[rand()%(r-l+1)+l];
    }

    void mysort(vector<int>& stock,int l,int r, int cnt)
    {
        if(l>=r) return;
        int key=getrand(stock,l,r);
        int left=l-1;
        int right=r+1;
        int i=l;
        while (i < right) 
        {
            if (stock[i] < key) 
            {
                swap(stock[i++], stock[++left]);
            }
             else if (stock[i] > key) 
            {
                swap(stock[i], stock[--right]);
            } 
            else 
            {
                i++;
            }
        }
        int a=left-l+1;
        int b=right-left-1;
        int c=r-right+1;
        if(a>cnt)
        {
            mysort(stock,l,left,cnt);
        }
        else if(a+b>=cnt)
        {
            return;
        }
        else
        {
            mysort(stock,right,r,cnt-a-b);
        }
    }
};
